﻿/**
 * @file array.c
 * @author septem (jsm920@outlook.com)
 * @brief @see array.h
 * @version 0.1
 * @date 2024-12-09
 * 
 * @copyright Copyright (c) 2024
 * 
 */
#include "array.h"

#if defined(_WIN32) && defined(_MSC_VER)
// #pragma execution_character_set("utf-8")
#define WIN32_LEAN_AND_MEAN // 预处理器宏定义，它告诉编译器仅包含Windows SDK中最常用的函数和数据类型，从而减小编译时间和生成的可执行文件大小。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <CRTDBG.H>
#elif defined(__linux__)
#include <stdio.h>
#include <stdlib.h> //malloc() realloc() free()
#include <string.h> // memset() memcpy() memmove()
#include <assert.h> // assert()
#endif

arrayiterator_t* ArrayIteratorInit2(arrayiterator_t* pai, array_t* pa, int pos)
{
    if(pa->cntElem == 0 || pos >= (int)pa->cntElem )
    {
        return NULL;
    }
    else if(pos < 0)
    {
        pos =  (int)pa->cntElem + pos;
        if(pos < 0)
        {
            return NULL;
        }
    }
    pai->pa = pa;
    arrayblock_t * _pab = pa->pabBeg;
    unsigned int _cv = 0; // 累加值 Cumulative value
    while(   _pab && _cv < pa->cntElem)
    {
        if( (unsigned int)pos < _pab->cntElem + _cv )
        {
            break;
        }
        _cv += _pab->cntElem;
        _pab = _pab->pabNext;
    }
    pai->pab = _pab;
    pai->pos = pos;
    pai->posAB = pos - _cv;
    // pai->pdata = (char*)_pab->data + (pos - _cv)* pa->szMemElem;
    return pai;
}

arrayiterator_t* ArrayIteratorPrev(arrayiterator_t* pai)
{
    if(pai->posAB > 0 )
    {
        pai->posAB --;
        pai->pos --;
        return pai;
    }
    else
    {
        if(pai->pab->pabPrev && pai->pab->pabPrev->cntElem)
        {
            pai->pab = pai->pab->pabPrev;
            pai->posAB  = pai->pab->cntElem - 1;
            pai->pos --;
            return pai;
        }
    }
    return NULL;
}
arrayiterator_t* ArrayIteratorNext(arrayiterator_t* pai)
{
    if(pai->posAB < pai->pab->cntElem - 1 )
    {
        pai->posAB ++;
        pai->pos++;
        return pai;
    }
    else
    {
        if(pai->pab->pabNext && pai->pab->pabNext->cntElem)
        {
            pai->pab = pai->pab->pabNext;
            pai->posAB  = 0;
            pai->pos++;
            return pai;
        }
    }
    return NULL;
}

/**
 * @brief 向 pa->pabEnd 尾部插入一个 可容下 cntElem 的 arrayblock_t。
 * 
 * @param pa 
 * @return arrayblock_t* 
 */
arrayblock_t* ArrayBlockMalloc(array_t* pa, unsigned int cntElem)
{
    if(cntElem < pa->cntGrow)
    {
        cntElem = pa->cntGrow;
    }
    arrayblock_t* _pab = (arrayblock_t*)malloc( sizeof(arrayblock_t) + cntElem * pa->szElem);
    if(_pab == NULL)
    {
        return NULL;
    }
    pa->pabEnd->pabNext = _pab;
    _pab->pabPrev = pa->pabEnd;
    _pab->pabNext = NULL;
    pa->pabEnd = _pab;
    pa->cntCapacity += cntElem;
    _pab->cntCapacity = cntElem;
    _pab->cntElem = 0;
    return _pab;
}

array_t* ArrayMalloc(unsigned int szElem, unsigned int cnt)
{
    if(cnt < 8) {cnt = 8;}
    unsigned int szMem = ArrayMemUsed(szElem,cnt);
    array_t* _pa = (array_t*)malloc(szMem);
    if(_pa == NULL)
    {
        return NULL;
    }
    // memset(_pa,0,szMem);
    // _pa->signNeedFree = 1;
    return ArrayInit(_pa, szElem, cnt);
}
void ArrayFree(array_t* pa)
{
    ArrayUninit(pa);
    free(pa);
}
array_t* ArrayInit(array_t* pa, unsigned int szElem, unsigned int cnt)
{
    pa->pabBeg = (arrayblock_t*)((char*)pa + sizeof(array_t));
    pa->pabEnd = pa->pabBeg;
    pa->pabTail = pa->pabBeg;
    pa->cntElem = 0;
    pa->cntCapacity = cnt;
    pa->cntGrow = cnt;
    pa->szElem = szElem;
    // pa->szMemElem = ArrayMemElemUsed(szElem);
    pa->pabBeg->cntCapacity = cnt;
    pa->pabBeg->pabPrev = NULL;
    pa->pabBeg->pabNext = NULL;
    pa->pabBeg->cntElem = 0;
    return pa;
}
void ArrayUninit(array_t* pa)
{
    struct arrayblock_t* _pab = pa->pabBeg;
    arrayblock_t* _pabNotMalloc = (arrayblock_t*)((char*)pa + sizeof(array_t));
    while (_pab)
    {
        struct arrayblock_t* pabt = _pab->pabNext;
        _pab->pabNext = NULL; _pab->pabPrev = NULL;
        if(_pab != _pabNotMalloc)
        {
            free(_pab);
        }
        _pab = pabt;
    }
    memset(pa, 0,sizeof(array_t)); //防止重复调用 ArrayUninit
}

array_t* ArrayShrink(array_t* pa)
{
    array_t* _patmp = NULL;
    if(pa->pabBeg != pa->pabEnd) // 存在多个块
    {
        arrayblock_t* pabs = pa->pabBeg;
        void* pdata = _patmp->pabBeg->data;
        if(pa->pabBeg == (arrayblock_t*)((char*)pa + sizeof(array_t)))
        {
            _patmp = (array_t*)ArrayMalloc( pa->szElem, pa->cntElem);
            if(_patmp)
            {
                unsigned int sz = pabs->cntElem * pa->szElem;
                memcpy(pdata, pabs->data, sz);
                pabs = pabs->pabNext;
                pdata = (char*)pdata + sz;
            }
        }
        else
        {
            _patmp = (array_t*)realloc(pa, ArrayMemUsed(pa->szElem, pa->cntElem));
        }
        if(_patmp)
        {
            while (pabs)
            {
                unsigned int sz = pabs->cntElem * pa->szElem;
                memcpy(pdata, pabs->data, sz);
                pabs = pabs->pabNext;
                pdata = (char*)pdata + sz;
            }
        }
    }
    return _patmp;
}

array_t* ArrayAssign(array_t* pa, array_t* pa2, unsigned int from,unsigned int cnt)
{
    // 1, 检查 from 和 cnt 的合法性
    if(from >= pa2->cntElem)
    {
        return pa;
    }
    if(from + cnt > pa2->cntElem) //修正 cnt,防止超过数量
    {
        cnt  = pa2->cntElem - from;
    }
    // 2, 检查 pa->是否可以保存 cnt 数量的元素
    arrayblock_t* _pab = pa->pabBeg;
    unsigned int _cntHole = 0; // 块中空洞累计数量
    while ( _pab != pa->pabTail) 
    {
        _cntHole += (_pab->cntCapacity - _pab->cntElem);
        _pab = _pab->pabNext;
    }
    if(pa->cntElem + _cntHole + cnt > pa->cntCapacity) // pa 尾部无法容下这么多元素, 再次申请一个足够大的块
    {
        if(NULL == ArrayBlockMalloc(pa, (pa->cntCapacity - (pa->cntElem + _cntHole + cnt))))
        {
            return NULL;
        }
    }
    // 3, 计算 准备开始拷贝的位置 _pab2 的偏移 _pos2
    _pab = pa->pabTail;
    arrayblock_t* _pab2 = pa2->pabBeg; // pa2 准备拷贝的块
    unsigned int _pos1 = _pab->cntElem; // pa 准备接收的位置偏移
    unsigned int _pos2; //  pa2 准备拷贝的块的偏移
    unsigned int _cv2 = 0; // pa2 累计计数
    while (_pab2  && _cv2 < pa2->cntElem)
    {
        if( from < _pab2->cntElem + _cv2)
        {
            _pos2 = _cv2 - from;
            break;
        }
        _cv2 += _pab2->cntElem;
        _pab2 = _pab2->pabNext;
    }
    // 拷贝 pa2 到 pa 
    while (cnt > 0)
    {
        if(_pos1>=pa->cntCapacity)
        {
            _pab = _pab->pabNext;
            _pos1 = _pab->cntElem;
        }
        if(_pos2 >= pa2->cntElem)
        {
            _pab2 = _pab2->pabNext;
            _pos2 = 0;
        }
        unsigned int cntCanReceive = _pab->cntCapacity - _pos1; //能接收多少拷贝
        unsigned int cntCanOffer = _pab2->cntElem - _pos2; //能给出多少用于拷贝
        unsigned int cntCopy = 0;
        if(cntCanReceive < cntCanOffer)
        { // _pab消耗完,移到下一个;
            cntCopy = cntCanReceive > cnt ? cnt:cntCanReceive;
            memcpy(_pab->data+ pa->szElem*_pos1, _pab2->data+pa2->szElem*_pos2,pa->szElem*cntCopy);
            cnt -= cntCopy;
            _pab = _pab->pabNext;
            _pos1 = 0;
            _pos2 += cntCopy;
        }
        else if(cntCanReceive == cntCanOffer)
        { // _pab和_pab2都消耗完,移到下一个;
            cntCopy = cntCanReceive > cnt ? cnt:cntCanReceive;
            memcpy(_pab->data+ pa->szElem*_pos1, _pab2->data+pa2->szElem*_pos2,pa->szElem*cntCopy);
            cnt -= cntCopy;
            _pab = _pab->pabNext;
            _pos1 = 0;
            _pab2 = _pab2->pabNext;
            _pos2 =0;
        }
        else
        { // _pab2 消耗完,移到下一个;
            cntCopy = cntCanOffer > cnt ? cnt:cntCanOffer;
            memcpy(_pab->data+ pa->szElem*_pos1, _pab2->data+pa2->szElem*_pos2,pa->szElem*cntCopy);
            cnt -= cntCopy;
            _pos1 += cntCopy;
            _pab2 = _pab2->pabNext;
            _pos2 =0;
        }
    }
    return pa;
}
array_t* ArraySub(array_t* pa, unsigned int from,unsigned int cnt)
{
    return NULL;
}

void* ArrayPush(array_t* pa, void* data )
{
    arrayblock_t* _pab = pa->pabTail;
    if( _pab->cntElem >= _pab->cntCapacity)
    {
        if(_pab->pabNext)
        {
            _pab = _pab->pabNext;
            assert(_pab->cntElem == 0);
        }
        else
        {
            _pab = ArrayBlockMalloc(pa, 0);
            if(_pab == NULL)
            {
                return NULL;
            }            
        }
        pa->pabTail = _pab;
    }
    void* _pdata = (char*)_pab->data + _pab->cntElem * pa->szElem;
    _pab->cntElem ++;
    pa->cntElem ++;
    if(data)
    {
        memcpy(_pdata, data, pa->szElem);
    }
    return _pdata;
}

void ArrayPop(array_t* pa)
{
    assert(pa->cntElem == 0 || pa->pabTail->cntElem >0); // 如果pa 有元素pa->pabBeg 到 pa->pabTail必需有无素
    if(pa->pabTail->cntElem > 1)
    {
        pa->pabTail->cntElem--;
        pa->cntElem--;
    }
    else if(pa->pabTail->cntElem == 1)
    {
        pa->pabTail->cntElem = 0;
        pa->cntElem--;
        if(pa->pabTail->pabPrev)
        {
            pa->pabTail = pa->pabTail->pabPrev;
        }
    }
}

void* ArrayUnshift(array_t* pa, void* data )
{
    if(pa->pabBeg->cntElem < pa->pabBeg->cntCapacity) // 第一个块有空间
    {
        if(pa->pabBeg->cntElem > 0)
        {
            memmove(pa->pabBeg->data + pa->szElem, pa->pabBeg->data, pa->pabBeg->cntElem * pa->szElem);
        }
    }
    else // 第一个块没有空间
    {
        arrayblock_t * pab;
        if(pa->pabEnd->cntElem == 0) //如果最后一个块是空块，那么把这个块移动到块首
        {
            assert(pa->pabEnd != pa->pabBeg); // 因为第一个块有空间不能执行
            assert(pa->pabEnd->pabPrev!=NULL); //
            pab =  pa->pabEnd;
            pa->pabEnd = pa->pabEnd->pabPrev;
            pa->pabEnd->pabNext = NULL;
        }
        else
        {
            pab = (arrayblock_t*)malloc( sizeof(arrayblock_t) + pa->cntGrow * pa->szElem );
            if(pab == NULL)
            {
                return NULL;
            } 
            pa->cntCapacity += pa->cntGrow;
            pab->cntCapacity = pa->cntGrow;
            pab->cntElem = 0;
        }
        pab->pabPrev = NULL;
        pab->pabNext = pa->pabBeg;
        pa->pabBeg->pabPrev = pab;
        pa->pabBeg = pab;
    }
    pa->pabBeg->cntElem ++; pa->cntElem ++;
    if(data)
    {
        memcpy(pa->pabBeg->data, data, pa->szElem);
    }
    return pa->pabBeg->data;
}

void ArrayShift(array_t* pa)
{
    if(pa->pabBeg->cntElem > 1)
    {
        pa->pabBeg->cntElem--;pa->cntElem--;
        memmove(pa->pabBeg->data, pa->pabBeg->data+ pa->szElem, pa->pabBeg->cntElem*pa->szElem);
    }
    else if(pa->pabBeg->cntElem == 1)
    {
        pa->pabBeg->cntElem--;pa->cntElem--;
        if(pa->pabBeg != pa->pabEnd)
        {
            arrayblock_t * pab = pa->pabBeg;
            pa->pabBeg = pa->pabBeg->pabNext;
            pa->pabBeg->pabPrev = NULL;
            pa->pabEnd->pabNext = pab;
            pab->pabPrev = pa->pabEnd;
            pab->pabNext = NULL;
            pa->pabEnd = pab;
        }
    }
}

/**
 * @brief 扩大一个块的空间
 * 
 * @param pa 
 * @param ppab  
 * @param grow 
 * @param pos 当 (*ppab) 不可移动时,重新申请一个块,替换这个块, pos指保存在这个块中的原有数据的偏移
 * @return arrayblock_t* 
 */
arrayblock_t* _ArrayGrowBlock(array_t* pa, arrayblock_t** ppab, unsigned int grow, unsigned int pos)
{
    arrayblock_t* _pab = NULL;
    if(grow < pa->cntGrow){ grow = pa->cntGrow;}
    if( (char*)pa + sizeof(array_t) == (char*)(*ppab)) //如果此块是 array_t* 申请时附加的一个块,那么这个块不可移动,需要再申请一个块替换这个块
    { //申请一个新块替换这个块
        arrayblock_t* _pab = (arrayblock_t*)malloc(sizeof(arrayblock_t) + pa->szElem * ((*ppab)->cntCapacity + grow));
        if(_pab == NULL)
        {
            return NULL;
        }
        _pab->cntCapacity = (*ppab)->cntCapacity + grow;
        if((*ppab)->pabPrev) {(*ppab)->pabPrev->pabNext = _pab;}
        _pab->pabPrev = (*ppab)->pabPrev;
        if((*ppab)->pabNext) {(*ppab)->pabNext->pabPrev = _pab;}
        _pab->pabNext =  (*ppab)->pabNext;
        if(pa->pabTail == (*ppab)) {pa->pabTail = _pab;}
        if(pa->pabBeg == (*ppab)) {pa->pabBeg = _pab;}
        if(pa->pabEnd == (*ppab)) {pa->pabEnd = _pab;}
        if(pos == (*ppab)->cntElem)// 位置正好在 块的尾部位置(最后一个元素的后面),//仅把块移动到 pa->pabEnd
        {
            _pab->cntElem = (*ppab)->cntElem;
            memcpy(_pab->data, (*ppab)->data, pa->szElem * (*ppab)->cntElem);
            (*ppab)->cntElem = 0;
            if(pa->pabEnd != (*ppab))
            {
                pa->pabEnd->pabNext = (*ppab);
                (*ppab)->pabPrev = pa->pabEnd;
                pa->pabEnd = (*ppab);
                (*ppab)->pabNext = NULL;
            }
        }
        else
        { // 位置在 (*ppab) 已有元素内部,需要移动已有元素
            _pab->cntElem = pos;
            if(pos != 0 && pos < (*ppab)->cntElem) //需要移动一部分数据,并且把 (*ppab) 块插入pabNew的后面
            {
                memcpy(_pab->data, (*ppab)->data, pa->szElem * pos);
                memmove((*ppab)->data, (*ppab)->data + pa->szElem * pos, pa->szElem * ((*ppab)->cntElem - pos));
                (*ppab)->cntElem -= pos;
            }   
            (*ppab)->pabPrev = _pab;
            (*ppab)->pabNext = _pab->pabNext;
            _pab->pabNext = (*ppab);
            if(pa->pabTail == _pab) {pa->pabTail = (*ppab);}
            if(pa->pabEnd == _pab) {pa->pabEnd = (*ppab);}      
        }

        (*ppab) = _pab;
    }
    else
    {
        _pab = (arrayblock_t*)realloc((*ppab), sizeof(arrayblock_t) + pa->szElem * ((*ppab)->cntCapacity + grow));
        if(_pab == NULL)
        {
            return NULL;
        }
        if(_pab != (*ppab)) // 空间有移动
        {
            if((*ppab)->pabPrev) {(*ppab)->pabPrev->pabNext = _pab;}
            if((*ppab)->pabNext) {(*ppab)->pabNext->pabPrev = _pab;}
            if(pa->pabTail == (*ppab)) {pa->pabTail = _pab;}
            if(pa->pabBeg == (*ppab)) {pa->pabBeg = _pab;}
            if(pa->pabEnd == (*ppab)) {pa->pabEnd = _pab;}
            (*ppab) = _pab;
        }
        (*ppab)->cntCapacity += grow;        
    }
    pa->cntCapacity += grow;
    return (*ppab);
}

void* ArrayInsert(array_t* pa,void* data,unsigned int from, unsigned int cnt)
{
    if(from > pa->cntElem) // 把大于 pa->cntElem 都转换为 为 pa->cntElem ，此段不可删除
    {
        from = pa->cntElem;
    }
    void* _pdata = NULL; // 插入元素成功后,第一个元素的位置
    arrayblock_t* _pab = pa->pabBeg; // 要插入块的位置
    unsigned int _cv = 0; // 用于计算 _pab 之前的元素的累加量
    unsigned int _cntBlockSpace = 0; //保存块中的空位置数量
    while (_pab && _cv < pa->cntElem )
    {
        if(from <= _pab->cntElem + _cv) // 在这个块元素中间插入,或 后面插入
        {
            unsigned int posBlock = from - _cv; // 在 _pab 块中的 偏移
            // 检查本块，如果空间不够，就扩大块空间直到块空间足够（最少扩大一个pa->cntGrow）
            if(from < pa->cntElem)//不是在 pa->pabTail 的尾部插入
            {
                unsigned int cntCanInsert = _pab->cntCapacity - _pab->cntElem; // _pab 可插入的元素的数量
                if(cntCanInsert < cnt)
                { // _pab 此块不足够保存新元素，直接realloc 这个块至可以保存元素,最小 realloc pa->cntGrow 大小
                    if(_ArrayGrowBlock(pa, &_pab, cnt - cntCanInsert,posBlock) == NULL)
                    {
                        return NULL;
                    }
                }
                _pdata = _pab->data + pa->szElem * posBlock;
                if(posBlock != _pab->cntElem)
                {//在 _pab 的前面插入，需移动现有元素
                    _pdata = _pab->data + pa->szElem * posBlock;
                    memmove(((char*)_pdata) + pa->szElem * cnt, _pdata, pa->szElem * (_pab->cntElem - posBlock));
                }
                _pab->cntElem += cnt;
                if(data)
                {
                    memcpy(_pdata, data, pa->szElem * cnt);
                }
            }
            else
            {// 是在 pa->pabTail 的尾部插入
                if(pa->cntCapacity - pa->cntElem - _cntBlockSpace < cnt) //后面的块空间不足以保存新的元素,扩大_ pab
                {
                    if(_ArrayGrowBlock(pa, &_pab, cnt - (pa->cntCapacity - pa->cntElem - _cntBlockSpace),posBlock) == NULL)
                    {
                        return NULL;
                    }
                }
                unsigned int cntCanInsert = _pab->cntCapacity - _pab->cntElem; // _pab 可插入的元素的数量
                if(cntCanInsert == 0) // pa->pabTail 这个块已经满了,需要移动到下一个块,此时_pab->pabNext 不可能为 NULL
                {
                    assert(_pab->pabNext != NULL);
                    _pab = _pab->pabNext;
                    _pdata = _pab->data + pa->szElem * _pab->cntElem;
                }
                else
                {
                    _pdata = _pab->data + pa->szElem * _pab->cntElem;
                }
                unsigned int cntTmp = cnt;
                while (/*_pab && */cntTmp)
                {
                    assert(_pab != NULL);
                    cntCanInsert = _pab->cntCapacity - _pab->cntElem; // _pab 可插入的元素的数量
                    if(cntCanInsert >= cntTmp)
                    {
                        if(data)
                        {
                            memcpy(_pab->data + pa->szElem * _pab->cntElem, data, pa->szElem * cntTmp);
                        }
                        _pab->cntElem += cntTmp;
                        cntTmp = 0;
                        break;
                    }
                    if(data)
                    {
                        memcpy(_pab->data + pa->szElem * _pab->cntElem, data, pa->szElem * cntCanInsert);
                        data = (void*)((char*)data + pa->szElem * cntCanInsert);
                    }
                    _pab->cntElem += cntCanInsert;
                    cntTmp -= cntCanInsert;
                    assert(_pab->cntElem == _pab->cntCapacity);
                    _pab = _pab->pabNext;
                }
            }
            break;
        }
        _cntBlockSpace += (_pab->cntCapacity - _pab->cntElem);
        _cv += _pab->cntElem;
        _pab = _pab->pabNext;
    }
    pa->cntElem += cnt;
    return _pdata;
}

void ArrayErase(array_t* pa,unsigned int from, unsigned int cnt)
{
    if(from>= pa->cntElem || cnt == 0) //排除空的 array_t 或超过范围删除或删除0长度
    {
        return;
    }
    unsigned int cntElemToDel = 0; // 需要从 pa->cntElem 中删除的数量
    unsigned int _posAS = from; //要删除的元素 在 array_t 中起始偏移，包含这个元素 
    unsigned int _posAE = from + cnt; //要删除的元素 在 array_t 中结束偏移，不包含这个元素 
    // if(_posAE > pa->cntElem) {_posAE = pa->cntElem;} 
    arrayblock_t* _pabStart = pa->pabBeg; // 要删除的元素起始偏移所在块
    arrayblock_t* _pabEnd = NULL; // 要删除的元素结束偏移所在块
    unsigned int _posBS = -1; //要删除的元素 在 _pabStart 起始偏移
    unsigned int _posBE = -1; //要删除的元素 在 _pabEnd 结束偏移
    unsigned int _cv = 0; // 前面每个块元素数量的累加值 Cumulative value
    arrayblock_t* _pabEmptyStart = NULL; //被清空开始的块
    arrayblock_t* _pabEmptyEnd = NULL; //被清空结束的块
    int _cntElemToZero = 0; // 被清零的块的计数 
    while (_pabStart && _cv < pa->cntElem) // 有_cv < pa->cntElem 约束， _pabStart 只能走到 pa->pabTail
    {
        if(_posAS < _pabStart->cntElem + _cv) // 发现 _posAS 在 当前 _pabStart 范围内
        {
            _posBS = _posAS - _cv; // 计算 块内偏移
            unsigned int cntCanDel = _pabStart->cntElem - _posBS; // 本块可以用来被
            if( cnt < cntCanDel) // _pabStart 的 _posBS 元素之后的元素没有删完,需要把后面的元素向前移动,然后返回
            { // 删除操作只发生在 _pabStart内部,并且后面没有删完,后面还有
                unsigned int _posBSEnd = _posBS + cnt; 
                // 把后面的移动到前面
                memmove(_pabStart->data + pa->szElem * _posBS, 
                        _pabStart->data + pa->szElem * _posBSEnd, 
                        pa->szElem * (_pabStart->cntElem - _posBSEnd)); 
                _pabStart->cntElem -= cnt;
                pa->cntElem -= cnt;
                return;
            }
            else if(cnt == cntCanDel) // _pabStart 的 _posBS 元素之后的元素正好删完,cnt也用完
            {
                pa->cntElem -= cnt;
                _pabStart->cntElem -= cnt;
                if(_pabStart->cntElem == 0) // _pabStart 块被清空,需要把此块移动到 pa->pabEnd 之后
                {
                    assert(_posBS == 0);//如果 _posBS 起始偏移为0 cntElem 也一定为0
                    _pabEmptyStart = _pabStart;
                    break;
                }
                return;
            }
            else  // cnt > cntCanDel 情况, _pabStart 的 _posBS 元素之后全部删除了 cnt还没有用完
            {
                _cv += _pabStart->cntElem; //在此累加 _cv,然后再修改 _pabStart->cntElem 值
                cntElemToDel += cntCanDel;
                _pabStart->cntElem -= cntCanDel;
                if(_pabStart->cntElem == 0) // _pabStart 块被清空,需要把此块移动到 pa->pabEnd 之后
                {
                    if(_pabStart == pa->pabTail) // 应对只有一个块,但是删除超过 结尾
                    {
                        pa->pabTail = _pabStart->pabPrev ? _pabStart->pabPrev:pa->pabBeg;
                        pa->cntElem -= cntElemToDel;
                        return;
                    }
                    assert(_posBS == 0);//如果 _posBS 起始偏移为0 cntElem 也一定为0
                    _pabEmptyStart = _pabStart;
                }
                cnt -= cntCanDel; // 消耗 cnt 值
                _pabEnd = _pabStart->pabNext;
                while (_pabEnd && _cv < pa->cntElem)// 有_cv < pa->cntElem 约束，_pabEnd 只能走到 pa->pabTail
                {
                    if(_posAE < _pabEnd->cntElem + _cv) //处理 删除到 [1,_pabEnd->cntElem-1] 的情况
                    {
                        _posBE = _posAE - _cv; 
                        assert (_posBE != 0&&_posBE != _pabEnd->cntElem); // 结束偏移不应为0或到_pabEnd->cntElem, 所以结束块 _pabEnd 至少有一个元素
                        memmove(_pabEnd->data,_pabEnd->data+ pa->szElem*_posBE, pa->szElem*(_pabEnd->cntElem - _posBE));
                        cntElemToDel += _posBE;
                        _pabEnd->cntElem -= _posBE;
                        pa->cntElem -= cntElemToDel;
                        break; 
                    }
                    else
                    {
                        cnt -= _pabEnd->cntElem;
                        _cv += _pabEnd->cntElem;
                        cntElemToDel += _pabEnd->cntElem;
                        _pabEnd->cntElem = 0; // 中间的所有块 元素数量清零
                        if(_pabEmptyStart != NULL){_pabEmptyEnd = _pabEnd;}else{_pabEmptyStart = _pabEnd;} // 可能出现第一块没有删除但后面块全部删除的情况
                        if(cnt == 0 || pa->pabTail == _pabEnd) //如果此块正好删到结束就跳出
                        {
                            pa->cntElem -= cntElemToDel;
                            if(pa->pabTail == _pabEnd) // 如果正好删到pa->pabTail,说明删除到结束
                            {
                                pa->pabTail = _pabEmptyStart->pabPrev?_pabEmptyStart->pabPrev:_pabEmptyStart;
                                return; 
                            }
                            break;
                        }
                    }
                    _pabEnd = _pabEnd->pabNext;
                }
            }
            break;
        }
        _cv+=_pabStart->cntElem;
        _pabStart = _pabStart->pabNext;
    }
    // 移动空块到 pa->pabEnd 之后, 注意 空块移动需要配合上面的代码,其它地方使用不能直接复制过去,没有考虑到全部情况
    if(_pabEmptyStart && (!_pabEmptyEnd)) //仅移动 _pabEmptyStart 一个块
    {
        if(_pabEmptyStart->pabNext != NULL) // pabNext 如果为 NULL 说明只有一个块,就不用移动,因此判断 不为NULL的情况
        {
            _pabEmptyStart->pabNext->pabPrev =_pabEmptyStart->pabPrev;
            if(_pabEmptyStart->pabPrev)
            {
                _pabEmptyStart->pabPrev->pabNext = _pabEmptyStart->pabNext;
            }
            else 
            {
                pa->pabBeg = _pabEmptyStart->pabNext;
            }
            pa->pabEnd->pabNext = _pabEmptyStart;
            _pabEmptyStart->pabPrev = pa->pabEnd;
            _pabEmptyStart->pabNext = NULL;
            pa->pabEnd = _pabEmptyStart;
        }
    }
    else if(_pabEmptyEnd) // 移动一串值
    {
        assert(_pabEmptyStart && _pabEmptyStart != _pabEmptyEnd); // 只要 _pabEmptyEnd 有值, _pabEmptyStart 肯定有值
        assert(_pabEmptyStart->pabNext != NULL);
        if(_pabEmptyStart->pabPrev)
        {
            _pabEmptyStart->pabPrev->pabNext = _pabEmptyEnd->pabNext;
            _pabEmptyEnd->pabNext->pabPrev = _pabEmptyStart->pabPrev;
        }
        else 
        {
            pa->pabBeg = _pabEmptyEnd->pabNext;
            pa->pabBeg->pabPrev = NULL;
        }
        pa->pabEnd->pabNext = _pabEmptyStart;
        _pabEmptyStart->pabPrev = pa->pabEnd;
        _pabEmptyEnd->pabNext = NULL;
        pa->pabEnd = _pabEmptyEnd;
    }
}
void ArrayClear(array_t* pa)
{
    arrayblock_t* _pab = pa->pabBeg;
    for(;_pab;_pab=_pab->pabNext)
    {
        _pab->cntElem = 0;
    }
    pa->cntElem = 0;
}
int ArrayResize(array_t* pa, unsigned int cnt)
{
    return 0;
}
void ArraySwap(array_t* pa, unsigned int pos1, unsigned int pos2)
{

}
void ArraySort(array_t* pa, int(*compar)(const void*,const void*))
{
    
}
array_t* ArrayReserve(array_t* pa, unsigned int cnt)
{
    return NULL;
}
void* ArrayAt(array_t* pa, int pos)
{
    if(pos < 0)
    {
        pos =  (int)pa->cntElem + pos;
    }
    return ArrayAt2(pa, (unsigned int)pos);
}

void* ArrayAt2(array_t* pa, unsigned int pos)
{
    if( pos >=0 && pos < pa->cntElem)
    {
        arrayblock_t * pab = pa->pabBeg;
        unsigned int cv = 0; // 累加值 Cumulative value
        while(   pab && cv < pa->cntElem)
        {
            if( pos < pab->cntElem + cv )
            {
                break;
            }
            cv += pab->cntElem;
            pab = pab->pabNext;
        }
        return pab->data + (pos - cv ) * pa->szElem;
    }
    return NULL;
}

void* ArrayFront(array_t* pa)
{
    return pa->cntElem ? pa->pabBeg->data : NULL;
}

void* ArrayBack(array_t* pa)
{
    return pa->cntElem ? ((char*)pa->pabTail->data + (pa->pabTail->cntElem - 1) * pa->szElem):NULL;
}

void* ArrayNext(array_t* pa, void* pdata)
{
    for(arrayblock_t* pab = pa->pabTail; pab ; pab = pab->pabPrev)
    {
        char* pbeg = (char*)pab->data;
        char* pend = pbeg + pa->szElem * pab->cntElem;
        if( pbeg <= (char*)pdata && (char*)pdata < pend ) // 指针在范围内且差值是整数倍
        {
            unsigned int diff = (unsigned int)((char*)pdata - pbeg);
            if(diff % pa->szElem == 0) //差值是整数倍，说明是正确的对象指针
            {
                unsigned int pos = (unsigned int)diff / pa->szElem;
                if(pos + 1 == pab->cntElem )
                {
                    if( pab->pabNext && pab->pabNext->cntElem)
                    {
                        return pab->pabNext->data;
                    }
                }
                else
                {
                    return (char*)pdata + pa->szElem;
                }
            }
            break;
        }
    }
    return NULL;
}

void* ArrayPrev(array_t* pa,void* pdata)
{
    for(arrayblock_t* pab = pa->pabTail; pab ; pab = pab->pabPrev)
    {
        char* pbeg = (char*)pab->data;
        char* pend = pbeg + pa->szElem * pab->cntElem;
        if( pbeg <= (char*)pdata && (char*)pdata < pend ) // 指针在范围内且差值是整数倍
        {
            unsigned int diff = (unsigned int)((char*)pdata - pbeg);
            if(diff % pa->szElem == 0) //差值是整数倍，说明是正确的对象指针
            {
                unsigned int pos = diff / pa->szElem;
                if(pos == 0 )
                {
                    if( pab->pabPrev )
                    {
                        return (char*)pab->pabPrev->data + pa->szElem * (pab->pabPrev->cntElem -1);
                    }
                }
                else
                {
                    return (char*)pdata - pa->szElem;
                }
            }
            break;
        }
    }
    return NULL;
}

#ifdef _DEBUG
void array_print_positive_order_int(array_t* pa)
{
    // 在 linux shell中 printf 打印\n时就会刷新输出缓存，但是在windows vscode 中必须调用 fflush(stdout); 才可以刷新输出缓存
    printf("PositiveOrder:%p-%p-%p-%u-%u-%u-%u\n", pa->pabBeg, pa->pabEnd, pa->pabTail, pa->cntCapacity, pa->cntElem, pa->szElem,pa->cntGrow);  fflush(stdout);
    for(arrayblock_t* pab = pa->pabBeg; pab != NULL; pab = pab->pabNext)
    {
        printf("%p:(%p-%p-%u-%u-%d)\n",pab,pab->pabPrev,pab->pabNext,pab->cntCapacity,pab->cntElem,*(int*)&pab->data); fflush(stdout);
    }
    int i = 0;
    for(arrayiterator_t* pai = ArrayIteratorInit(pa, 0); pai != NULL; pai = ArrayIteratorNext(pai) )
    {
        int *pi = (int*)ArrayIteratorDataPtr(pai);
        printf("% 6d ", *pi);fflush(stdout);
        if(i<9){i++;}else{printf("\n");i=0;}
    }
    if(i<10){printf("\n");fflush(stdout);} 
}
void array_print_negative_order_int(array_t* pa)
{
    printf("NegativeOrder:%p-%p-%p-%u-%u-%u-%u\n", pa->pabBeg, pa->pabEnd, pa->pabTail, pa->cntCapacity, pa->cntElem, pa->szElem,pa->cntGrow);  fflush(stdout);
    for(arrayblock_t* pab = pa->pabBeg; pab != NULL; pab = pab->pabNext)
    {
        printf("%p:(%p-%p-%u-%u-%d)\n",pab,pab->pabPrev,pab->pabNext,pab->cntCapacity,pab->cntElem,*(int*)&pab->data); fflush(stdout);
    }
    int i = 0;
    for(arrayiterator_t* pai = ArrayIteratorInit(pa, -1); pai != NULL; pai = ArrayIteratorPrev(pai) )
    {
        int *pi = (int*)ArrayIteratorDataPtr(pai);
        printf("% 6d ", *pi);fflush(stdout);
        if(i<9){i++;}else{printf("\n");i=0;}
    }
    if(i<10){printf("\n");fflush(stdout);} 
}

void array_print_int_by_at(array_t* pa)
{
    int i = 0;
    for(int j=0; j != (int)ArraySize(pa);j++)
    {
        int* pi = ArrayAt(pa, j);
        if(pi)
        {
            printf("% 6d ", *pi);fflush(stdout);
            if(i<9){i++;}else{printf("\n");i=0;}
        }
    }
    if(i<9){printf("\n");fflush(stdout);} 
    i = 0;
    for(int j = -1; j != -1-(int)ArraySize(pa);j--)
    {
        int* pi = ArrayAt(pa, j);
        if(pi)
        {
            printf("% 6d ", *pi);fflush(stdout);
            if(i<9){i++;}else{printf("\n");i=0;}
        }
    }
    if(i<9){printf("\n");fflush(stdout);} 
}
void print_int_by_at2(array_t* pa)
{
    int i = 0;
    for(unsigned int j=0; j != (int)ArraySize(pa);j++)
    {
        int* pi = ArrayAt2(pa, j);
        if(pi)
        {
            printf("% 6d ", *pi);fflush(stdout);
            if(i<9){i++;}else{printf("\n");i=0;}
        }
    }
    if(i<9){printf("\n");fflush(stdout);} 
}

#endif

/*****************************以下为 array2_t 相关代码*********************************/

array2_t* Array2Malloc(unsigned int szElem, unsigned int cnt)
{
    array2_t* _pa = (array2_t*)malloc(sizeof(array2_t));
    if(_pa)
    {
        // _pa->signNeedFree = 1;
        _pa = Array2Init(_pa, szElem, cnt);
        if(_pa )
        {
            return _pa;
        }
        free(_pa);
    }
    return NULL;
}
void Array2Free(array2_t* pa)
{
    Array2Uninit(pa);
    free(pa);
    // if(pa->signNeedFree)
    // {
    //     free(pa);
    // }
}
array2_t* Array2Init(array2_t* pa,  unsigned int szElem, unsigned int cnt)
{
    pa->cntCapacity = cnt;
    pa->cntElem = 0;
    pa->szElem = szElem;
    pa->cntGrow = cnt;
    pa->pdata = malloc(szElem * cnt);
    if(pa->pdata )
    {
        return pa;
    }
    return NULL;
}

void Array2Uninit(array2_t* pa)
{
    if(pa->pdata){free(pa->pdata);pa->pdata = NULL;}
}
void* Array2Push(array2_t* pa, void* data)
{
    if(pa->cntElem >= pa->cntCapacity)
    {
        void* ptmp = realloc(pa->pdata, (pa->cntCapacity + pa->cntGrow) * pa->szElem);
        if(ptmp == NULL)
        {
            return NULL;
        }
        pa->pdata = ptmp;
        pa->cntCapacity += pa->cntGrow;
    }
    void * pdst = (char*)pa->pdata + pa->cntElem * pa->szElem;
    if(data)
    {
        memcpy(pdst,data, pa->szElem);
    }
    pa->cntElem++;
    return pdst;
}
void Array2Pop(array2_t* pa)
{
    if(pa->cntElem)
    {
        pa->cntElem--;
    }
}

void Array2PopTo(array2_t* pa, void* pdata)
{
    assert((char*)pdata >= (char*)pa->pdata); //一定要是 栈空间中的数据
    assert(((char*)pdata - (char*)pa->pdata) % pa->szElem == 0); // 一定要是 pa->szElem 整数倍
    pa->cntElem -= (unsigned int)(((char*)pdata - (char*)pa->pdata)/pa->szElem);
}

void* Array2Insert(array2_t* pa,void* datas,unsigned int from, unsigned int cnt)
{
    if(from >= pa->cntElem)
    {
        from = pa->cntElem;
    }
    if(pa->cntElem + cnt >= pa->cntCapacity)
    {
        unsigned int grow = pa->cntGrow;
        if(pa->cntElem + cnt - pa->cntCapacity> pa->cntGrow)
        {
            grow = pa->cntElem + cnt - pa->cntCapacity;
        }
        void* ptmp = realloc(pa->pdata, (pa->cntCapacity + grow) * pa->szElem);
        if(ptmp == NULL)
        {
            return NULL;
        }
        pa->pdata = ptmp;
        pa->cntCapacity += grow;
    }
    if(from < pa->cntElem)
    {
        memcpy((char*)pa->pdata + (from + cnt)*pa->szElem ,(char*)pa->pdata + from * pa->szElem, (pa->cntElem-from)* pa->szElem);
    }
    if(datas)
    {
        memcpy((char*)pa->pdata + (from + cnt)*pa->szElem, datas, cnt * pa->szElem);
    }
    pa->cntElem += cnt;
    return (char*)pa->pdata + (from + cnt)*pa->szElem;
}

void* Array2Erase(array2_t* pa,unsigned int from, unsigned int cnt)
{
    if(from >= pa->cntElem)
    {
        return NULL;
    }
    else if(from + cnt >= pa->cntElem)
    {
        pa->cntElem =  from + 1;
        return NULL;
    }
    memcpy((char*)pa->pdata + from * pa->szElem, (char*)pa->pdata + (from + cnt)*pa->szElem, (pa->cntElem-from-cnt)* pa->szElem);
    pa->cntElem -= cnt;
    return (char*)pa->pdata + from * pa->szElem;
}

void* Array2At(array2_t* pa, int pos)
{
    if(pos < 0)
    {
        //将 pos 转换为 正数
        pos = pos + (int)pa->cntElem;
        if(pos < 0)
        {
            return NULL;
        }
    }
    return Array2At2(pa,pos);
}

void* Array2At2(array2_t* pa, unsigned int pos)
{
    if(pos >= pa->cntElem)
    {
        return NULL;
    }
    return (void*)((char*)pa->pdata + pos * pa->szElem);
}

unsigned int Array2Search(array2_t* pa, const void* ptr, int (*compar)(const void*, const void*))
{
    for(int i = 0; i != pa->cntElem; i++)
    {
        if(0 == compar(ptr, ((char*)pa->pdata + i * pa->szElem)))
        {
            return i;
        }
    }
    return -1;
}

void* Array2Prev(array2_t* pa, void* pdata)
{
    assert((char*)pdata >= (char*)pa->pdata); //一定要是 栈空间中的数据
    assert(((char*)pdata - (char*)pa->pdata) % pa->szElem == 0); // 一定要是 pa->szElem 整数倍
    return ((char*)pdata - pa->szElem >= (char*)pa->pdata)? ((char*)pdata - pa->szElem ):NULL;
}

void* Array2Next(array2_t* pa, void* pdata)
{
    assert((char*)pdata >= (char*)pa->pdata); //一定要是 栈空间中的数据
    assert(((char*)pdata - (char*)pa->pdata) % pa->szElem == 0); // 一定要是 pa->szElem 整数倍
    return ((char*)pdata + pa->szElem >= (char*)pa->pdata)? ((char*)pdata + pa->szElem ):NULL;
}

unsigned int Array2Pos (array2_t* pa, void* ptr)
{
    unsigned int diff = (unsigned int)((char*)(ptr) - (char*)(pa)->pdata);
    unsigned int pos = diff / pa->szElem;
    if(diff % pa->szElem != 0 || pos >= pa->cntElem)
    {
        return -1;
    }
    return pos;
}